%% I am LaTeX document
\documentclass[a4paper,11pt]{article}
\bibliographystyle{plain}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage[breaklinks=true]{hyperref}
\author{Peter Høgh Steffensen, 20082410\\
Allan Stisen, 20083311\\
Kristian Kongsted, 20081434\\
Jon Korsgaard Sorensen, 20083030}
\title{Pervasive Positioning\\
Mandatory Project 2}
\date{}
\begin{document}
\maketitle

\tableofcontents


\section{Description of the program and the experiments}

\subsection{The design and implementation choices}
\subsubsection{Periodic reporting strategy}
This strategy does periodically subscripe to GPS fixes and after receiving a fix
it unsubscribes, with a timer. This is due to how android has facilitated the
GPS functionality and that we're using android version 2.1 as a base ground,
where the method
\begin{verbatim}
requestSingleUpdate(...)
\end{verbatim} is not available and therefore this workaround has been introduced. 
\subsubsection{Distance-based reporting strategy}
This reporting strategy is one of the simplest. It registers a listener to the GPS and every time a fix is received it checks how far the device has travelled. If the travelled distance exceeds the threshold a message is send to the server. The GPS fixes seems to be updating around a timeslot of one second.     
\subsubsection{Maximum speed distance based reporting strategy}
Accordingly to a fixed speed and threshold this strategy computes how long time
it will take the user to exceed this threshold. The simple equation, $time =
\frac{distance}{speed} $ will calculate the time needed for the user to exceed
this.
\subsubsection{Accelerometer based approach}
Before introducing the next two strategies a description of how the
accelerometer is used is needed. Basically the mandatory excercise with
accelerometer solution and one optional solution both uses the principles
from\cite{thiagarajan2011accurate}. They argue that the accelerometer is
basically so noisy that it can only itself be used to detect if there's moment
or not. So first of all the accelerometer is only a part of a bigger set of
sensor that hints about movement in their system, but their methods is
applicable to this situation because we only need hints of the device is moving
or not.
First of all the sensor can at some times make high spikes (if for example the
phone is picked up). These spikes is ignored until the system can back to rest
which can be detected with some more of their methods.

The article describes solutions to the iPhone where there's a static sampling
rate, which does not exist at the android framework. We use the same time slots,
1 second time slots, as in the article but the frequency is not guaranteed at
all, and we have discovered different frequencies from device to device, and
they aren't even static on the same device.

For each time window instead of rely on the magnitude of accelerations and
orientation of the phone they rely on deviations on each measurement. Comparing
each deviation with a threshold can result a short-lived outlier, so to get away
with these a EWMA filter is used for each measurement.

We have been using a threshold value at $0.15$, since it seems to be a lot of
noise in the devices and across devices. Even when laying static and flat on a
table some devices show small peek values around $0.1$. So this threshold value
should be generated and used only pr. device. Because if the threshold is to
high then you might not discover a movement and if it's to low then the extra
computation is not worth it.

This approach where the accelerometer is only used as a 1 bit indicating
movement or not, is only an advantage regarding to the power expensive GPS
receiver. So that this sensor can be turned of if we're not moving. If the
device is considered to be moving then the GPS is used as described in the
strategy.

\subsubsection{Movement-aware}
This strategy operates like the distance-based reporting strategy. So it uses
the GPS fixes to see if the distance threshold has been exceeded if it has it
sends a report otherwise it waits for the next fix. The accelerometer is only
used to turn off these fixes such that if the device doesn't detect any movement
then it unsubscribes the GPS fixes.
\subsubsection{Maximum-speed combined and movement aware}
This optional strategy uses the combination of two of the methods above.
Accordingly to a fixed speed and threshold this strategy computes how long time
it will take the user to exceed this threshold. The simple equation, $time =
\frac{distance}{speed} $ will calculate the time needed as in one of the former
strategies. In this strategy the hint of the accelerometer is used to minimize
the number of GPS fixes when the device is in a still mode.
The design choice that has been made in the combination of the two strategies is
he following. We're just using the maximum speed with a distance threshold as
normal, and before we're requesting a GPS fix we're using the boolean from our
accelerometer based approach to see if we're moving or not. If the device is
moving then it will make a request and if not it won't. This is somehow a simple
approach and can actually be lacking of accuracy if the user make short brake
when the timer is fired off. Then the device will not make a GPS fix, but if the
user moves aging then the user actually could brake the threshold.

So another solution on how to combine these two strategies would be first if the
device is moving then use the normal maximum speed distance threshold strategy.
But each time the accelerometer makes a hint about that the device have gone
into not moving mode, then compare the last time a GPS fix was requested or the
device was starting to moving accordingly to the accelerometer. Take the value
of the two which was the latest and subtract it from the time that it should
take to exceed the threshold and store it until the device is moving again and
use that as a threshold until a GPS fix is received, then it should precede as
normal. This is a little less simple then the former and that is the reason for
why it haven't been implemented.


\subsection{How to use the program}
We have written or server part in PHP. It accepts the requests send from each
strategy in the android application and writes a placemark to a file, which is
located in the data/ folder where the filename is ``strategy-name''-kml.xml. To
import the it into google earth, change the extension to .kml. The server also
writes a log file for each strategy used that contains a line for each request
recieved, and the unix timestamp for the time it was send. 

The kml file generated contains all the placemarks for a given strategy. These
placemarks holds the gps position in the discrption and a timestamp of the time
the gps location was obtained. 

To use the program, simply choose the strategy on the android application and
start it. The server will generate the resulting kml files for the requests send
from the phone.

The php-schript is located at http://daimi.au.dk/~kongsted/GPSPlotter.php and
the data files can be obtained from http://daimi.au.dk/~kongsted/data .  

\section{Google Earth screenshots for each scenario}

\subsection{Strategy descriptions}
\begin{enumerate}
\item{}Periodic reporting strategy with a time interval of 1 second.
\item{}Distance-based reporting strategy with distance configured as 50
meters.
\item{}Maximum-speed distance-based reporting strategy with distance configured
as 50 meters and maximum speed 10.44 m/s (Usain Bolt, Berlin 2009).
\item{}Maximum-speed distance-based reporting strategy with distance
configured as 50 meters and maximum speed 2 m/s.
\item{}Movement-aware (accelerometer) distance-based reporting strategy with
distance configured as 50 meters.
\item{}An optional strategy that uses both the maximum-speed and
accelerometer-based optimizations. Maximum speed configured as 2 m/s.
\end{enumerate}

\subsection{Strategy 1}
\begin{center}
\includegraphics[scale=0.365]{periodic.png}
\end{center}

\subsection{Strategy 2}
\begin{center}
\includegraphics[scale=0.365]{distancebased.png}
\end{center}

\subsection{Strategy 3}
\begin{center}
\includegraphics[scale=0.365]{configmaxspeedUB.png}
\end{center}

\subsection{Strategy 4}
\begin{center}
\includegraphics[scale=0.365]{configmax50m2ms.png}
\end{center}

\subsection{Strategy 5}
\begin{center}
\includegraphics[scale=0.365]{distanceBwithAcc.png}
\end{center}

\subsection{Strategy 6}
\begin{center}
\includegraphics[scale=0.365]{distancesmartwAcc.png}
\end{center}

\subsection{Comments on the results}
We ran our program using three different devices under conditions which could be
described as very good. The location was the parking lot above Storcenter Nord
and the time was approximately 20.30 in the evening. There was almost no cars on
the parking lot and the weather was clear. However, we still got a few GPS
errors.

Strategy 1 got a GPS fix every second, which seems a bit too much when just
walking. This strategy could maybe provide a good result if accuracy is very
important and if one is traveling fast. In our situation the energy consumption
is too high compared to the other strategies.

Strategy 2 gets all GPS fixes possible and only shows a position every 50
meters. This is obviously not an optimal strategy in our situation. This
strategy makes sense almost only if the energy consumption used to transfer data
is much higher than the energy consumption used to get a GPS fix.

Strategy 3 is optimized for a movement speed of 10.44 m/s. When walking it may
produce a little too many positions. A good property of this strategy is also
that it uses all the GPS fixes received and does not try to use the GPS too
much.

Strategy 4 is like strategy 3, but is optimized for a movement speed of 2.2 m/s.
This is a nice strategy for walking, as few GPS fixes are requested and all
fixes are used to output the position.

Strategy 5 is like strategy 2, but implements the use of the accelerometer,
which is a nice idea. However, the distance of 50 meters is, in our opinion,
too much to give a detailed trail. Also, it has the same disadvantages as
strategy 2 considering GPS spamming - but is only does this when the
accelerometer senses movement.

Strategy 6 is a mix between strategy 4 and 5 with the best of both strategies
when walking. It saves energy by only activating when the accelerometer senses
movement, is optimized for walking speed, and does not spam the GPS. And our
results show that it is very precise.



\section{Scenario list}

\begin{center}
\begin{tabular}{ | r | r | r | r | r | r | }
\hline
Strategy & GPS fixes & Uplink msgs & Time span & GPS fixes/sec & Uplink
msgs/sec\\ \hline
1 & 528 & 528 & 10m26s & 0.843 & 0.843\\ \hline
2 & 623 & 7 & 10m26s & 0.995 & 0.011\\ \hline
3 & 104 & 104 & 12m15s & 0.141 & 0.141\\ \hline
4 & 24 & 24 & 10m26s & 0.038 & 0.038\\ \hline
5 & 420 & 7 & 12m15s & 0.571 & 0.009\\ \hline
6 & 21 & 21 & 12m15s & 0.029 & 0.029\\ \hline
\end{tabular}
\end{center}

\subsection{Comments on the entries}


\bibliography{references}


\end{document}